package com.剑指offer.第四章;

/**
 * 在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向了它的子链表，并且子链表也是一个双向链表
 * 它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。
 */
public class 展平多级双向链表 {

    /**
     * @return
     */
    public static ListNode resolve(ListNode head) {
        ListNode node = flattenGetTail(head);
        return node;
    }

    public static ListNode flattenGetTail(ListNode head) {
        ListNode node = head;
        ListNode tail = null;
        while (node != null) {
            ListNode next = node.next;
            if (node.child != null) {
                ListNode child = node.child;
                ListNode endNode = flattenGetTail(node.child);

                node.child = null;
                node.next = child;
                child.pre = node;
                endNode.next = next;
                // 双向
                if (next != null) {
                    next.pre = endNode;
                }
            } else {
                // 记录每次的节点
                tail = node;
            }
            node = next;
        }
        return tail;
    }

    public static void main(String[] args) {

    }

}
